package algorithm.sort;

/**
 * @Author liuhaoqi
 * @Date 2020/12/29 17:16
 * @Version 1.0
 */
public class QuickSort2 {
    public static void main(String[] args) {
        int[] arr = {1, 5, 6, 7, 8, 9, 324, 3, 211, 0};
        int low = 0;
        int high = arr.length - 1;
        sort(arr, low, high);
        for (int i : arr) {
            System.out.println(i);
        }
    }

    public static void sort(int[] arr, int low, int high) {
        if (low < high) {
            int position = getPosition(arr, low, high);
            sort(arr, low, position - 1);
            sort(arr, position + 1, high);
        }
    }

    public static int getPosition(int[] arr, int low, int high) {
        int key = arr[low];
        while (low < high) {
            //如果不加等于号 ，就会一直进行交换，跳不出循环，导致栈溢出！ 等号必须加上
            while (arr[high] >= key && high > low) {
                high--;
            }
            arr[low] = arr[high];
            while (arr[low] <= key && low < high) {
                low++;
            }
            arr[high] = arr[low];
        }
        arr[low] = key;
        return low;
    }
}
